The present invention relates to a method and an apparatus for generating half-tone dots for reproducing images on an ink-jet printer and, more particularly, to the generation of half-tone dots capable of conveying a large number of different tonal values.
In the art of printing it is generally known to reproduce images that originally contain areas of different tonal values by means of a screen-like two-dimensional pattern of inked (e.g. black) dots at regular intervals, the dots and the spaces therebetween being of variable proportions. Such reproduction is also referred to as half-tone reproduction; accordingly, the screen pattern and the dots are also referred to with the modifier "half-tone". In order to distinguish between half-tone dots and a different type of dot, to be discussed herebelow, the term half-tone spot, or, briefly, spot, will be used in the sequel. For a good quality image, there are, typically, about 150 half-tone spots to the inch. Color printing is typically effected by superposing four images, each with one of the four process-color inks. In order to minimize moire pattern effects, the screen patterns of the four images are mutually inclined at certain angles.
Digital printing devices typically generate an image by marking the printed medium, such as paper, with a regular pattern of contiguous parallel lines, each line varying between the values--"on" (marking) and "off" (blank)--according to the image. In some devices, such as ink-jet printers and printers using pulsed lasers, to be collectively referred to as discrete-dot marking devices, each marking line inherently consists of a series of contiguous elementary dots (to be referred to, briefly, as dots), each dot having a binary value (marking or non-marking--corresponding to having ink applied or not applied at its respective location). In some other devices, such as those using continuously radiating lasers for marking, a marked segment of a line may be continuous, but the algorithm for switching between marking--and non-marking states is based, in effect, on a model of contiguous discrete bi-valued dots--thus, again, forming a two-dimensional array of dots. The necessarily finite spatial frequency of marking lines, and of dots within a marking line, causes certain limitations on achievable image quality--especially with respect to half-tone images, as will be discussed herebelow, and it is the challenge of improving image quality in face of such limitations that is answered by the present invention. It is noted that there are also digital marking devices that, rather than directly print an image on a print medium, serve to create a latent image on a printing plate, which subsequently serves in a printing press. Most of what is discussed and disclosed in the present specification applies to such marking devices as well.
There are many methods known in the art for converting a digitally-represented multi-valued image into a half-tone pattern that is suitable for reproduction by a binary marking device (which conversion process is also referred to as digital screening, or, in short, screening). According to one such method (to be referred to herebelow as method A), in common usage and useful for a marking scheme that is based on the model of discrete dots along marking lines, there is stored a two-dimensional matrix of threshold values, one value per dot location, which represents the screen function at the appropriate angular orientation. For each dot of the half-tone image the corresponding threshold value is compared with the original image value and the result of the comparison determines the (binary) dot value. For certain angles of orientation (namely those whose tangent is a rational number), the screen function can be made to be repetitive in both dimensions, so that a threshold matrix corresponding to only one (repetitive) segment of the screen function need be stored. This method has several drawbacks:
(1) It is practically limited to rational-tangent angles; PA1 (2) for desirable rational-tangent angles, a relatively large amount of values (corresponding to a large segment, as well as to the number of such different screen angles to be implemented) need be stored;, and PA1 (3) there is a variance in size and shape among neighboring spots, resulting in visual artifacts. PA1 (1) The screening function is represented by a matrix of groups of values, each group relating to a possible dot within the section and consisting of a plurality of threshold values and, possibly some control values. Prior to marking any dot, the respective group of values is retrieved and compared with a corresponding pixel value. According to the result, a drive pulse is either not generated or is generated synchronously with a clock pulse or generated at some specified interval from a clock pulse. PA1 (2) The screening function is represented by a plurality of matrices, each related to a possible pixel value and consisting of an array of marking values--one value per possible dot within the section. Prior to marking any dot, the matrix corresponding to the pixel value is retrieved and the respective marking value specifies whether the respective drive pulse should be generated and, if so--at what positive or negative interval, if at all, relative to a clock pulse. PA1 (3) The screening function is represented by a plurality of arrays, each related to a possible pixel value and consisting of groups of position values, one group per marking line within the section, each value related to one boundary dot within the section. During the marking of any line, the array corresponding to each pixel value, along the line, is retrieved and a boundary drive pulse is generated for each position value along the respective line, at a commensurate timing (relative to the section). Additional pulses are generated, synchronously with clock pulses, between pairs of boundary pulses. According to a variation of this method, the additional pulses are generated so that all intervals between pulses are equal. PA1 (4) The screening function is represented by a matrix of threshold vaues. During the marking of any line, A sequence of threshold vaues corresponding to the line is retrieved fromm storage and converted to an analog signal. At the same time, a sequence of pixel values corresponding to the line is obtained and, likewise, converted to an analog signal. The two analog signals are continuously compared and a binary marking signal is generated accordingly. For each transition of the marking signal, a drive pulse is generated. Additionally, a drive pulse is generated at each clock pulse that occurs while the marking signal is in a "mark" state, except at close proximity to a transition. PA1 defining over the plane of the image a raster of regularly spaced grid lines and, along each line, a pattern of grid points, spaced at a constant pitch, PA1 applying drive pulses to the device, for marking dots on the medium, each dot to be uniquely associated with one of the grid points, the pulses being timed so that the center of at least one boundary dot is essentially displaced from its associated grid point and so that the centers of all dots within a marked area that are not boundary dots lie essentially at corresponding grid points. PA1 generating a train of regularly spaced clock pulses, their period being equal to the constant pitch divided by the scanning velocity; PA1 for each dot to be marked with its center at a grid point, generating a drive pulse in synchronism with one of the clock pulses, and for each dot to be marked with its center displaced from its associated grid point, generating a drive pulse at a commensurate time difference from a corresponding one of the clock pulses. PA1 generating a train of regularly spaced clock pulses, their period being equal to the constant pitch divided by the scanning velocity; PA1 generating a drive pulse upon each state transition, in the binary signal, and a drive pulse for each of the clock pulses that occurs during a marking state of the binary signal and that is not closer than a specified minimal interval to the time of any state transition in the binary signal. PA1 applying drive pulses to the device, for selectively marking dots on the medium, the pulses being timed so that the center-to-center distance, along a line, within at least one first pair of adjacent marked dots is essentially different from the center-to-center distance, along a line, within at least one second pair of adjacent marked dots along a line. PA1 defining, along each line, a plurality of grid points, spaced at a constant pitch, and uniquely associating each marked dot with one of the grid points; PA1 further timing the drive pulses so that the centers of both dots of any of the at least one second pair lie essentially at corresponding grid points and the center of at least one boundary dot lies essentially displaced from its corresponding grid point. PA1 defining a screening function, over the area of the rendered image, as a repetitive array of adjacent identical elementary screening functions, each defined over a section of the area; PA1 for each grid point within any of the sections, storing a plurality of threshold values, in conformity with the elementary screening function; and PA1 for each grid point along a line: PA1 for each possible pixel value, storing an array of marking values, one marking value for each grid point within the section, in conformity with the elementary screening function; PA1 for each grid point along a line: PA1 for each possible pixel value, storing a plurality of position values in conformity with the elementary screening function, each position value representing a position of the center of a boundary dot with respect to the section; PA1 for each repetition of the section along each marking line, retrieving corresponding position values from storage; PA1 for each position value retrieved, applying a drive pulse to the device, timed so as to mark a boundary dot at a corresponding position along the respective marking line, the position not being necessarily at a grid point; PA1 applying additional drive pulses to the device, timed so as to mark corresponding additional dots between sequential boundary dots, each additional dot being centered on its associated grid point or, alternatively, all additional dots and the boundary dots are essentially equidistant. PA1 generating a continuous screening signal, representing a screening function; PA1 generating a train of regularly spaced clock pulses, their period being equal to the constant pitch divided by the scanning velocity; and PA1 for each raster line: PA1 a marking device, operative to scan the medium, along each line of a raster of parallel lines, at constant scanning velocity and further operative, in response to, and synchronously with, drive pulses applied thereto, to selectively mark dots on the medium, each dot uniquely corresponding to an applied drive pulse, contiguous marked dots forming marked areas and any dot in a marked area that is adjacent to an unmarked area being a boundary dot; and PA1 a pulse generator, for applying drive pulses to the marking device, including: PA1 a drive pulse that is not necessarily synchronous with any of the clock pulses for each state transition in the binary signal; and PA1 a drive pulse synchronous with any of the clock pulses that occurs during a marking state of the binary signal and not closer than a specified minimal interval to the time of any state transition in the binary signal. PA1 further includes N comparators and a logic circuit, receptive to outputs of all the comparators, and PA1 is further operative to retrieve from the storage one complete group of the threshold values just prior to each of the clock pulses and to apply each of the retrieved threshold values to a corresponding one of the comparators; PA1 address a location in the storage that corresponds to the value of the respective pixel; PA1 retrieve from an addressed storage location a marking value, corresponding to the dot; and PA1 control the outputting of a corresponding drive pulse and its timing, with respect to a nearest clock pules, according to the retrieved marking value. PA1 to address a location in the storage that corresponds to the respective pixel; PA1 to retrieve from an addressed storage location all position values relating to the position of the line, with respect to the section; PA1 for each retrieved value, to cause the pulse gating circuit to output a drive pulse that is not necessarily synchronous with any of the clocked pules, it being a boundary drive pulse, whose timing with respect to the scanning of the section, is commensurate with the retrieved position value; and PA1 while the device is scanning any area to be marked, to cause the pulse gating circuit to output additional drive pulses, synchronously with corresponding ones of the clock pulses. PA1 the analog signal generator and connected at its output to the pulse gating circuit; PA1 the screen generator being further operative, with respect to any line, along which the device is scanning and with respect to any of the sections across which the device is scanning, to: PA1 the comparator being operative to compare the image signal with the threshold signal and accordingly to generate a binary signal, which alternates between a marking state and a non-marking state; and PA1 the pulse gating circuit being further operative to output;
Another known rational-tangent angled screening method suitable for discrete dot marking (to be referred to herebelow as method B), has a binary dot pattern over a (repetitive) segment stored for each possible image value. For each image pixel, the dot pattern corresponding to its value and to its relative position in the segment is read out and fed to the marking device. This method shares the first three drawbacks of method A, listed hereabove, and even requires greater storage capacity, but, advantageously, is not limited to monotoniccally increasing spots; rather, there is total independence between the spot shapes at various tone values.
The discrete dot structure entails another drawback for screening, though it is not very pronounced for high resolution devices, such as those using laser beams for marking. In the latter there are, typically, about 2000 lines to the inch, and that same frequency of dots (if indeed so structured). With such devices, each spot of a half-tone screen of, said, 175 spots to the inch (which is typically used for high quality printing) contains, on the average, about (2000/175).times.(2000/175)=131 dots. Since the dots are binary valued, each spot can thus have 132 values of proportional area (from totally blank to totally marking). Thus image details as fine as the size of a single spot can be reproduced at any of only 132 shades of gray; and, conversely, an area of an image that has uniformly a shade of any value, out of only 132 values, can be uniformly reproduced down to the screen structure and excluding small variations among neighboring spots due to the screening method (such as the one described hereabove). With devices of continuous marking capability, such as those utilizing continuous-radiation lasers, the number of tonal values and the spot uniformity can be further increased if the dot structure along lines is abandoned and screening methods, such as those taught by the following three patents, are adopted.
U.S. Pat. No. 5,519,792 teaches storing the screen function as a matrix of threshold values that is independent of the marking grid structure and of the orientation angle of the half-tone pattern to be marked, reading out values from the stored matrix along a line that corresponds to a marking line and to the orientation angle, comparing them to a corresponding image value and, where, between any successive points, the sense of the comparison switches, calculating, by interpolation, the exact location, along the marking line, of a boundary between marking- and non-marking segments.
U.S. Pat. No. 5,526,143 teaches a screening technique similar to that of the '792 patent, except that the succession of threshold values is calculated on the fly and that it, as well as the succession of image values, are converted to corresponding successions of analog values; these are interpolated, to create corresponding smooth signals, which are then mutually compared, the point at which the sense of the comparison switches determining the boundary between marking- and non-marking segments.
U.S. Pat. No. 5,691,828 teaches storing the screen function, at any given orientation angle, as relative locations of boundary points of spots along lines parallel to the marking lines (the storage being arranged according to tonal values corresponding to various spot shapes and sizes) and reading out these values to determine boundary points along any marking line.
The methods of the three patents, briefly described hereabove, are suitable for continuous marking devices, such as those using a continuous laser beam, and their main advantage is the possibility of delineating each half-tone spot at a much greater resolution than implied by the spatial line frequency of the marking device. They largely overcome the drawbacks listed for the previously described methods (A and B) and enable defining the size and shape of any marked spot with any desired precision and thus reproduce any desired number of tonal values.
In the case of an ink-jet printer, each elementary marking dot is, typically, produced by an elementary drop of ink, contiguous dots being produced by consecutive drops that are ejected from a nozzle at regular intervals while the nozzle travels with respect to the medium along a marking line. Usually, there is a plurality of nozzles, from which drops are ejected along corresponding parallel marking lines. The distance between adjacent marking lines determines the spatial dot frequency in one dimension (referred to as the cross-scan dimension), while the ratio of drop ejection frequency to the scanning speed (which is the speed of travel of the nozzles with respect to the medium) determines the spatial dot frequency along the other (in-scan) dimension. In current art, the highest cross-scan frequency is about 720 dots to the inch and it is the common practice to make this also to be the in-scan frequency. Higher spatial frequencies are possible, but at the expense of higher equipment complexity and, thus, costs, or at the expense of lower overall marking speed. For example, the in-scan spatial frequency may be doubled (as is, indeed, offered in some models), by halving the scan speed--which, of course, halves the overall marking rate.
In a half-tone screen of, say, 144 spots to the inch, produced by a 720 dots/inch device, each spot contains, on the average, 5.times.5=25 dots. Each spot can thus reproduce only 26 shades. In order to reproduce a greater number of shades in an image, it is a common practice to obtain any desired shade value by averaging the values of a group of adjacent spots. For example, for the mentioned screen of 144 spots to the inch, one can group every 3.times.3 adjacent spots, to jointly reproduce any of 9.times.26=234 shades. When using rational-tangent angle screening methods (such as methods A and B hereabove), this multi-spot grouping for achieving a large number of shades is part of the designed screening function within a (repetitive) segment. In practice, all such grouping, and the distribution of shade values among spots in a group,, disadvantageously produce a pattern of commensurately lower spatial frequencies, which may become visible under certain circumstances. It may become particularly visible where the image contains some fine detail of a repetitive nature, which may beat (i.e. cause moire patterns) with the grouping pattern. It is, therefore, desirable to be able to finely vary the size of each half-tone spot so that it can, by itself, reproduce any of a large number of shades (as would, to some extent, be possible with higher resolution devices, as was discussed hereabove with respect to laser-based devices). Because of the discrete nature of the ink drops, the dot structure along lines is inherent to this printing technique (that is--ink-jet printers are of the discrete-dot marking type), so that the improved half-tone screening methods of the '792, the '143 and the '828 patents (which call for finely positioning the boundaries between marking and non-marking segments), described hereabove, cannot be directly applied. It is noted that this problem becomes more acute the lower the inherent resolution (i.e. spatial dot frequency) of the ink-jet printer. It is further noted that a similar problem may exist in any low-resolution marking device, such as a thermal printer or a magneto-graphic device, if the mark switching along a line is done only at time points that correspond essentially to whole dot positions, thus also producing discrete dots. It is further noted that the problem may, to some extent, be also significant with discrete-dot marking devices of inherently high resolution, such as those using pulsed lasers, and may become serious if, for some reasons, it proves to be advantageous to operate them at lower resolutions (for example--to increase overall marking speed).
For such low resolution discrete-dot marking devices, it has been common practice to use irregular scattered dot patterns for half-tone rendering. There are many methods for creating such patterns, but all suffer, to a greater or lesser extent, from a fundamental drawback. namely that the patterns inherently contain relatively low spatial frequencies, which cause disturbing visual effects.
Another drawback of low-resolution marking devices is that inclined boundaries between marked and unmarked areas (e.g. edges of graphic objects), for example, as illustrated in FIG. 1A, are formed as stairs, which may be visible. Likewise, the boundaries of half-tone spots are formed as stairs, imparting to each spot a shape of a generally very irregular polygon, as shown, for example, in FIG. 1B. Such a shape typically includes protrusions and many near-right angles. Because of the complex nature of the interaction between the ink drops and the medium (e.g. paper), which includes joining of adjacent drops, on the one hand, and diffusion into the medium, on the other hand, such shapes tend to cause considerable non-linearity in the relation between the number of drops (i.e. nominal number of marking dots) and the actually marked area (or the obtained average optical density), as well as a great deal of variability. It is, therefore, desirable to produce half-tone spots that have as nearly regular shapes as possible. It is again noted that this problem becomes more acute with decreasing dot frequencies and may be common also with marking devices other than of the ink-jet type.
An obvious way to achieve more shade values, as well as to improve the shape of a spot, is to increase the spatial dot frequency. As was noted hereabove, it is possible to increase the spatial frequency, at least along the in-scan dimension, by slowing the scan rate or increasing the drop ejection frequency. Slowing the scan rate disadvantageously results in slower overall operation; increasing the drop frequency may be limited technologically. Both approaches result in increased ink density, which may be undesirable. U.S. Pat. No. 5,270,728 teaches a method to partially overcome the limitation on drop frequency and the increased density problem, while effectively doubling the in-scan dot frequency. According to this method, some (possible half) of the dots inside a marked area are deliberately set to blank value (i.e. the respective drops are inhibited from being ejected), while dots at the boundaries of such an area are made to always have a marking value. It is noted that even doubling the in-scan dot frequency (which seems to be the maximum achievable, in practice), while reducing some of the stairs effects at edges of objects and of half-tone spots, is still far from providing the desired possible number of shades per half-tone spot. In the aforementioned example of a 144 spots/inch screen, the number of shades would be only increased to 51.
U.S. Pat. No. 5,029,108 teaches a method for considerably reducing the stairs effects along edges of graphic objects, by modifying the size and relative position of certain dots along such edges, thus finely controlling the beginning and end of each dot and thereby creating commensurately smaller stairs. This method is, again, particularly applicable to electrophotographic devices (which use lasers for marking) and is generally not applicable to ink-jet devices, since it is difficult to appreciably vary the size of ejected drops, especially when their rate is already set near the highest possible value.
It is, moreover, noted that both the '728 and the '108 patents address only the issue of the formation of edges of binary-valued graphic elements and not, specifically, the issues attending the formation of half-tone spots, as discussed hereabove. In particular, they do not address the problem of the irregularly shaped spots (though they may indirectly and partially alleviate the problem) and, more importantly, do not address the problem of the limited number of shades reproducible by any one spot. The latter point may be illustrated by the following observation: Consider applying the method of either of the two patents to a half-tone image that has been screened according to the inherent resolution of the device; the edges of the spots would be modified according to the method and may indeed look somewhat smoother; their average positions, however, and therefore also their respective marking areas, will remain substantially unaltered, the marking areas still assuming one of the limited number of possible values.
There is thus a widely recognized need for, and it would be highly advantageous to have, a method for generating half-tone spots for low-dot-frequency marking devices, such as ink-jet printers, whereby the spots would have relatively regular shapes and their marking areas would assume any of a relatively large number of values.